package LC;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode.com/problems/course-schedule/description/
 * There are a total of n courses you have to take, labeled from 0 to n - 1.
 * Some courses may have prerequisites, for example to take course 0 you have to first take course 1,
 * which is expressed as a pair: [0,1]
 * Given the total number of courses and a list of prerequisite pairs,
 * is it possible for you to finish all courses?
 * For example:
 * 2, [[1,0]]
 * There are a total of 2 courses to take. To take course 1 you should have finished course 0.
 * So it is possible.
 * 2, [[1,0],[0,1]]
 * There are a total of 2 courses to take. To take course 1 you should have finished course 0,
 * and to take course 0 you should also have finished course 1. So it is impossible.
 * Note:
 * The input prerequisites is a graph represented by a list of edges, not adjacency matrices.
 * Read more about how a graph is represented.
 * You may assume that there are no duplicate edges in the input prerequisites.
 */
public class LC_207_CourseSchedule_List_Map {
    public static void main(String[] args) {
        int[][] prerequisites = {
                {1, 0},
                {0, 1}
        };
        int numCourses = 2;
        System.out.println(Solution.canFinish(numCourses, prerequisites));
    }

    static class Solution {
        static boolean canFinish(int numCourses, int[][] prerequisites) {
            HashMap<Integer, List<Integer>> maps = new HashMap<>();
            int[] indegree = new int[numCourses];
            int length = prerequisites.length;
            if (length <= 0) return true;
            for (int[] prerequisite : prerequisites) {
                int first = prerequisite[0];
                int second = prerequisite[1];
                if (!maps.containsKey(first))
                    maps.put(first, new LinkedList<>());
                maps.get(first).add(second);
                indegree[second]++;
            }
            List<Integer> list = new LinkedList<>();
            for (int i = 0; i < numCourses; i++) {
                if (indegree[i] == 0)
                    list.add(i);
            }
            while (list.size() > 0) {
                int val = list.get(0);
                indegree[val] = -1;
                list.remove(0);
                if (!maps.containsKey(val)) continue;
                List<Integer> tmpList = maps.get(val);
                for (Integer aTmpList : tmpList) {
                    int index = aTmpList;
                    indegree[index]--;
                    if (indegree[index] == 0)
                        list.add(index);
                }
            }
            for (int i = 0; i < numCourses; i++)
                if (indegree[i] != -1)
                    return false;
            return true;
        }
    }
}